#include <bits/stdc++.h>

using namespace std;

// 统计不同回文子序列
// 给你一个字符串s，返回s中不同的非空回文子序列个数
// 由于答案可能很大，请你将答案对10^9+7取余后返回
// 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/

class Solution 
{
public:
    int countPalindromicSubsequences(string s) 
    {
        const int MOD = 1e9 + 7;
        int n = s.size();
        // s[i] 仅包含 'a', 'b', 'c' 或 'd' 
        int last[4];
        memset(last, 0xff, sizeof last);
        // left[i] : i位置的左边和s[i]字符相等且最近的位置在哪，不存在就是-1
        int left[n];
        for(int i = 0; i < n; ++i)
        {
            left[i] = last[s[i] - 'a'];
            last[s[i] - 'a'] = i;
        }
        // right[i] : i位置的右边和s[i]字符相等且最近的位置在哪，不存在就是n
        for(int i = 0; i < 4; ++i) last[i] = n;
        int right[n];
        for(int i = n - 1; i >= 0; --i)
        {
            right[i] = last[s[i] - 'a'];
            last[s[i] - 'a'] = i;
        }
        // dp[i][j] : i...j范围上有多少不同的回文子序列
		// 如果i>j，那么认为是无效范围dp[i][j] = 0
        long dp[n][n];
        memset(dp, 0, sizeof dp);
        for(int i = 0; i < n; ++i) dp[i][i] = 1;
        for(int i = n - 2, l, r; i >= 0; --i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(s[i] != s[j])
                {
                    // a ..... b
					// i       j
					// 因为要取模，所以只要发生减操作就+mod，讲解041同余原理
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + MOD;
                }
                else
                {
                    // s[i] == s[j]
					// a......a
					// i      j
                    l = right[i], r = left[j];
                    if(l > r)
                    {
                        // i...j的内部没有s[i]字符
						// a....a
						// i    j
						// (i+1..j-1) + a(i+1..j-1)a + a + aa
						dp[i][j] = 2 * dp[i + 1][j - 1] + 2;
                    }
                    else if(l == r)
                    {
                        // i...j的内部有一个s[i]字符
						// a.....a......a
						// i     lr     j
						// (i+1..j-1) + a(i+1..j-1)a + aa
                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1;
                    }
                    else
                    {
                        // i...j的内部不只一个s[i]字符
						// a...a....这内部可能还有a但是不重要....a...a
						// i   l                             r   j
						// 因为要取模，所以只要发生减操作就+mod，讲解041同余原理
                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1] + MOD;
                    }
                }
                dp[i][j] %= MOD;
            }
        }
        return dp[0][n - 1];
    }
};